\chapter{Compilação Dinâmica e Compiladores JIT}
\label{compdyn}

\section{Compilação Dinâmica}

O termo ``compilação dinâmica'' refere-se a técnica de tradução de
código sob demanda. Ela têm sido utilizada para aumentar o desempenho
de aplicativos, gerando código em tempo de execução. Aplicações
variadas têm feito uso desta técnica \cite{holzle}, mas pode-se apontar
implementações de linguagens de programação como fator motivante para
a existência e evolução da mesma. A busca por
interpretadores mais rápidos fez surgir a idéia da compilação dinâmica
\cite{holzle}, pois, com ela, é possível reduzir o custo de avaliação de
instruções e também elimina-se o \textit{overhead} de decodificação de
instruções.
A emissão de código nativo não é um requisito dessa compilação, mas é
o foco do presente trabalho.

%XXX arrumar esse parágrafo
Características como tipos dinâmicos e estruturas de dados dinâmicas
incentivam a construção de interpretadores
\cite{trustworthycompilers} e, apesar de terem o tempo de execução
acrescido de 10 vezes \cite{plezbert} a até 1000 vezes
\cite{trustworthycompilers}, quando comparado a linguagens compiladas, as
facilidades fornecidas atraem usuários. Apesar do quesito performance
não ser o mais prioritário nessas linguagens, é fácil verificar que as
implementações destas linguagens costumam ser feitas em \texttt{C}
\cite{dyla1}. Logo,
aparentemente, a facilidade de desenvolvimento quer estar unida com
alto desempenho.
%XXX Falar do porque JIT pode ser aplicado melhor nessas linguagens

Linguagens interpretadas comumente apresentam-se como problemas a
compiladores estáticos, isso é devido a falta de informações no momento
da compilação \textit{offline} \cite{holzle}.
Entretanto, um compilador dinâmico tem acesso a todas informações
produzidas ao longo da execução.
Logo, é possível tratar dos problemas
introduzidos por linguagens de mais alto nível e produzir código
nativo que não seria possível, ou muito difícil, com compiladores
estáticos.

Estes tradutores podem ser construídos das mais variadas formas.
Em relação ao modo de operação dos compiladores dinâmicos, o trabalho
de \citeonline{plezbert} distingue 3 classes:
\begin{description}
  \item[JIT (Just in Time)]: O ambiente alterna entre a compilação sob
    demanda para código nativo e a execução do código nativo gerado;
    somente um das duas situações ocorre num dado momento
  \item[Compilação contínua]: Realiza compilação em tempo de execução
    mas não exatamente sob demanda. Esse modo tenta compilar o máximo
    de código em paralelo a execução em uma tentativa de disponibilizar
    código nativo quando ocorrer a chamada de um procedimento. Caso
    ocorra uma chamada para um procedimento que ainda não tenha sido
    compilado, pode-se utilizar o interpretador
  \item[Smart JIT]: Permite a execução mista entre máquina virtual e
    código nativo. Ao invocar um método, não necessariamente ocorre a
    compilação. Parâmetros precisam ser estabelecidos para determinar
    as condições que levam a emissão de código
\end{description}
Apesar desta diferenciação existir, diversos trabalhos
\cite{suganuma_oopsla_2001, suganuma_ibm, judo} têm utilizado o termo
JIT no lugar de \textit{Smart} JIT e o mesmo ocorre com o trabalho
corrente.

A consequência de utilizar um dos dois primeiros tipos acima, em
comparação ao terceiro, é a possibilidade de \textit{delay} na
inicialização do ambiente de execução. Isso ocorre porque logo
no inicio a máquina virtual possivelmente invoca muitos métodos.
Entretanto, qualquer um dos três
impacta no desempenho da aplicação visto que eles consomem tempo
de execução. Selecionar parâmetros adequados para compilação dinâmica
alivia esse problema, pois pode-se compilar somente procedimentos que
são muito executados. Um parâmetro que pode ser utilizado nesta
decisão é a quantidade de invocações de um
procedimento/método com decaimento ao longo do tempo \cite{holzle} ou
não. Este número também pode ser combinado com a quantidade de
repetições de laços executadas.

Tradicionalmente, compiladores JIT têm trabalhado com compilação de métodos
por inteiro. Entretanto, estes compiladores
dispõem da flexibilidade de decidir o que constitui sua
unidade de compilação. Trabalhos mais recentes descrevem o uso laços
\cite{jitcompunits}, \textit{traces}
\cite{jitcompunits} ou regiões \cite{regionunit} como alternativas a
funções completas para compilação. Estas três outras formas surgiram
como propostas de melhoria \cite{regionunit, jitcompunits} sobre o
método tradicional. Elas permitem
despender tempo de análise e geração de código somente em partes que
realmente são mais
frequentemente executadas. A compilação de regiões é uma generalização
daquela com uso de \textit{traces}, onde esta última é formada
por um único ponto de entrada e múltiplas saídas \cite{jitcompunits}
enquanto que a primeira trabalha sobre uma coleção arbitrária de
blocos básicos \cite{dragonbook}.

Compiladores dinâmicos podem ser otimizadores ou não. Entretanto, é
mais comum encontrar a primeira forma visto que a intenção é gerar
código para linguagens com recursos que consomem maior tempo de
execução. Também torna-se interessante o uso de técnicas de otimização somente
se o custo da compilação for dominado pelo ganho em desempenho.
 Sistemas mais robustos \cite{holzle, judo, suganuma_ibm}
que empregam estes compiladores têm feito uso de mais de um
compilador. Em um primeiro momento, a compilação ocorre com uso de um
tradutor que gera código de forma rápida mas não tão eficiente. Isso
reduz a ocorrência de pausas durante a execução. Ao
detectar que este código vem sendo frequentemente utilizado,
aplica-se um outro compilador que faz uso de otimizações mais
dispendiosas. A recompilação dinâmica \cite{holzle} também pode ser
utilizada com o intuito de remover otimizações e possibilitar a inspeção
de código.



\section{Compiladores JIT}


\subsection{Smalltalk--80}

A implementação da \texttt{Smalltalk-80} \cite{bluebook} de
\citeonline{deutsch84efficient} faz uso da compilação dinâmica para
transformar \textit{v-code} em código nativo (chamado de
\textit{n-code}). A motivação para empregar esta técnica teve relação
com os recursos da linguagem \texttt{Smalltalk}, como alocação dinâmica e
procedimentos universalmente polimórficos \cite{sebesta}, que são
difíceis de serem traduzidos de forma eficiente. Não foi feito uso do
modo misto (\textit{Smart JIT}), na ocorrência de uma chamada sempre
realiza-se primeiro geração de código nativo, caso ainda não exista,
para depois iniciar a execução do método.

Na época em que esta implementação ocorreu, haviam restrições severas
de memória. Por este motivo, o trabalho teve a preocupação de verificar
se o código nativo gerado seria paginado ou não. Caso isso viesse a
ocorrer, o código seria descartado e gerado novamente quando outra
invocação ao procedimento ocorresse. No presente trabalho, esse cuidado
não é tomado e não foi levado em consideração.

Durante esta implementação da \texttt{Smalltalk}, também houve a
preocupação em permitir a utilização de compiladores dinâmicos
variados, mas não todos ao mesmo tempo.
\citeonline{deutsch84efficient} descrevem duas implementações
que foram testadas, a primeira faz uso de otimizações \textit{peephole}
\cite{muchnick} esparsamente e obtém tamanho de código reduzido
quando comparado a outra. A segunda implementação é mais agressiva nas
otimizações aplicadas, aplicando a expansão \textit{in-line} até para
operações aritméticas e relacionais. Nessa configuração mais agressiva
foram obtidos os melhores resultados, chegando a um tempo quase 2
vezes menor comparando-se com o interpretador puro. O trabalho aqui
proposto alcança reduções maiores, mas apenas para um subconjunto
pequeno da linguagem ao passo em que a implementação de
\citeonline{deutsch84efficient} trabalha por completo na
especificação da linguagem envolvida.


\subsection{CACAO}

A CACAO \cite{cacao} é um compilador JIT para a linguagem
\texttt{Java} com foco no processador ALPHA \cite{alphaproc}.

Para construir sua representação intermediária, \textit{bytecodes}
\texttt{Java} são convertidos para uma forma de máquina de registradores. De
forma semelhante com o trabalho realizado, buscou-se converter uma
representação de máquina de pilha para outra que assemelha-se com a
arquitetura de um processador RISC (\textit{Reduced Instruction Set
  Computer}) \cite{risc}
\nomenclature{RISC}{Reduced Instruction Set Computer}.
Entretanto, o trabalho de \citeonline{cacao} tem a preocupação
de eliminar as ineficiências da máquina de pilha  (\textit{load} \&
\textit{store}) quando convertidas para registradores. O trabalho não
da detalhes sobre a alocação de registradores, mas menciona que é
feito de forma simples e rápida.

A arquitetura deste sistema ainda envolve a definição de um novo
\textit{layout} de objetos e métodos em \texttt{Java}, tornando o
acesso mais rápido e utilizando menos memória.

Com os \textit{benchmarks} utilizados, a CACAO obteve um desempenho de
até 85 vezes superior ao comparar-se com o interpretador JDK
(\textit{Java Development Kit}).
\nomenclature{JDK}{Java Development Kit}
A CACAO também foi testada
contra o compilador gcc \cite{gcc1} com uso da \textit{flag}
\verb!-03!, verificando-se que o tempo do compilador JIT foi
entre 1.01 e 1.66 vezes pior que aquele obtido com o gcc.

\subsection{Jikes RVM}

O projeto Jikes RVM (\textit{Research Virtual Machine}) \cite{jikes}
(até 2001 conhecida como Jalapeño JVM) teve como objetivos iniciais
suportar a arquitetura PowerPC \cite{powerpc} e fornecer uma JVM de
alto desempenho. Enquanto conhecida como Jalapeño JVM, sua
distribuição era trabalhosa devido as licenças estabelecidas
\cite{jikesrvm2}. A renomeação para Jikes RVM deveu-se a correções
neste processo, tornando-a em um projeto de código livre. Neste momento
também notou-se a necessidade de portar seu código para a arquitetura
IA-32 \cite{jikesrvm2}, pelas mesmas razões defendidas neste trabalho.

O trabalho de \citeonline{jikes}, descreve que a Jalapeño/Jikes é
escrita com a própria linguagem
\texttt{Java}. Para que não seja necessário o uso de outra máquina
virtual para iniciar sua execução, uma imagem de incialização
executável pré-compilada, contendo todos os serviços essenciais para
uma JVM, é criada para ser carregada em memória e então permitir sua
execução.

Esta máquina virtual não trabalha com interpretação de
\textit{bytecodes}, um compilador \textit{baseline} é utilizado para
compilar todos os métodos de forma rápida. Métodos executados muito
frequentemente são então recompilados com um compilador otimizador.
Este compilador otimizador trabalha com 3 representações
intermediárias: \begin{inparaenum}[(1)]
\item uma de alto nível independente de arquitetura e que
trabalha com transferência de registradores; \item outra de
baixo nível também independente mas com instruções semelhantes com as
de uma arquitetura RISC \cite{risc}; \item e uma a nível da máquina
alvo\end{inparaenum}.

O compilador otimizador trabalha com seleção de instruções por meio de
padrões em árvores \cite{instrselect} e a
alocação de registradores é feita através de uma variação do método
de varredura linear \cite{linear_scan_regalloc}. Otimizações de
eliminação de subexpressões comuns \cite{muchnick}, eliminação de
movimentação redundante, propagação de cópias \cite{muchnick},
eliminação de código morto \cite{allen_kennedy}, \textit{in-line} de
métodos, entre várias outras são aplicadas por este compilador.

Resultados do trabalho de \citeonline{jikes} demonstraram que, com a
implementação descrita da Jikes RVM para IA-32, a
utilização de alocação de registradores e seleção de instruções
produzem código até quase 2 vezes mais eficiente quando comparado a
compilação sem estas técnicas. O presente trabalho não
faz uso destas técnicas, mas espera-se que elas também colaborem com
o desempenho quando aplicadas.


\subsection{JUDO}

A JUDO \cite{judo} é uma outra JVM, ela faz uso
de compilação dinâmica com dois tipos de compiladores e coleta
informações em tempo de execução.

O primeiro desses compiladores é um
mais simples, que gera código rapidamente, destinado a compilação
de métodos invocados pela primeira vez. Durante a emissão de código,
instruções que coletam dados a cerca da execução são inseridas.
O segundo compilador é
invocado quando as informações coletadas indicarem que certos métodos
são executados muito frequentemente e, portanto, estes podem ser
beneficiados com a aplicação de otimizações.
Essa recompilação dinâmica
é feita com o intuito de balancear o tempo gasto na compilação com o tempo
efetivamente gasto na execução do programa.

As otimizações aplicadas incluem: eliminação de subexpressões comuns
\cite{muchnick} durante a construção da representação intermediária;
uma fase de verificação de pontos candidatos a \textit{in-line};
propagação de cópias; desdobramento de constantes \cite{muchnick};
eliminação de código morto e eliminação de verificação de subscritos em
\textit{array} \cite{boundcheck}. Também são feitas otimizações
\textit{offline} para inicialização de classes, \textit{cast} e
verificação de subscritos.

Este sistema foi projetado para trabalhar com
a compilação de métodos por inteiro, sendo esta a maior semelhança com
o trabalho proposto aqui.

De forma geral, a avaliação de performance indicou que o gerador de
código ágil (parecido, mas ainda mais avançado por inlcuir algumas
otimizações, com o proposto aqui) é o que apresenta pior performance
em relação as outras duas formas avaliadas:
\begin{inparaenum}[(1)] \item compilador otimizador sem
informações de tempo de execução; \item e outro que faz uso de recompilação
dinâmica\end{inparaenum}.

\subsection{IBM JDK}

O artigo de \citeonline{suganuma_ibm} exibe a evolução
de uma JVM desenvolvida na IBM que faz uso de compilação dinâmica com
foco na arquitetura IA-32, assim como este trabalho.

% XXX Citacao para DAG.
A IBM JDK (\textit{Java Development Kit}) utiliza 3 representações
intermediárias: \begin{inparaenum}[(1)] \item EBC
(\textit{Extended Bytecode})\nomenclature{EBC}{Extended Bytecode}; \item
quádruplas; \item DAG (\textit{Directed Acyclic Graph})\end{inparaenum}.
\nomenclature{DAG}{Directed Acyclic Graph}
A segunda destas equivale à utilizada no trabalho
em discussão, sendo baseada em registradores. A terceira também é
baseada em registradores mas faz uso da SSA (\textit{Static Single
  Assignment}) \cite{cytron}.
\nomenclature{SSA}{Static Single Assignment}

O compilador dinâmico desse sistema utiliza 3 níveis de compilações. A
cada nível mais otimizações vão sendo aplicadas, mas somente a de
nível 1 (que têm menor custo) é invocada na mesma \textit{thread} de
execução da aplicação. Os outros níveis de compilação ocorrem em
\textit{threads} separadas e somente são utilizadas se o sistema
de compilação detectar métodos que podem ser beneficiados por
elas. Para tomar essa decisão, um coletor periodicamente faz
amostragens do uso da CPU pelos métodos. O sistema mantém os métodos
que mais utilizam a CPU em uma lista ligada, ordenada por maior uso, e
os repassa para o compilador adequado em intervalos fixos. Não há
necessariamente uma transição do nível de compilação 1 para o 2 e
depois para o 3, pode ocorrer de, após passar pelo nível 1, um método
ser compilado diretamente no nível 3.

Uma variedade de otimizações são aplicadas em cada nível. Entre elas
estão a propagação de cópias e de constantes \cite{optconstprog},
eliminação de código morto,
eliminação de verificação de exceção \cite{optelimverifcexec} e
otimizações de laço \cite{muchnick}.

Os resultados demonstram que o compilador de nível 1 conseguiu obter o
segundo melhor desempenho em alguns casos, apesar de ser o que inclui
a menor quantidade de otimizações. Entretanto, a combinação entre os 3
níveis resultou na melhor performance em todos os testes realizados.

\subsection{Psyco}

O Psyco \cite{psyco} trabalha com compilação JIT juntamente com
especialização sobre a linguagem de programação \texttt{Python}.
Por especialização entende-se a tradução de um programa qualquer em
uma versão mais limitada do mesmo, na expectativa de que a versão
especializada seja mais eficiente do que a original. O Psyco trabalha,
especificamente, com especialização por avaliação parcial
\cite{partialeval}. Houve uma tentativa de aplicar um método
semelhante com a \texttt{Tcl} mas, diferentemente da linguagem
\texttt{Python} onde tipos são associados a valores, não conseguiu-se
determinar de forma eficiente o uso de tipos ao decorrer da aplicação.

Diversas versões de uma mesma função são possívelmente produzidas.
As funções a serem especializadas são selecionadas por meio de um
contador com decaímento exponencial, descrito em \cite{holzle}.

Em um \textit{benchmark} envolvendo aritmética com números inteiros, o
Psyco demonstrou melhoria de 109 vezes em relação ao interpretador
\texttt{Python} padrão. O mesmo teste em \texttt{C} executou 281 vezes
mais rápido que o interpretador. Ao medir o tempo de aritmética entre
números complexos, um melhoria de 3,65 vezes foi reportada. Essa
diminuição drástica entre os dois testes está relacionada com o fato
do Psyco conseguir representar algumas funções de forma mais
eficiente, especialmente aquelas envolvendo o uso de números inteiros.
